package structure.linkedList;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 地址：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 * <p>
 * 题目：剑指 Offer 11. 旋转数组的最小数字
 * <p>
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,4,5,1,2]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：[2,2,2,0,1]
 * 输出：0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Leetcode_Sword_Offer_06 {
    public static void main(String[] args) {

        ListNode node = new ListNode(1);
        node.next = new ListNode(3);
        node.next.next = new ListNode(2);
        int[] ints = reversePrint(node);
        for (int anInt : ints) {
            System.out.println(anInt);
        }


    }

    /**
     * 解法2：
     * 思路： 使用两遍循环来实现，效率确实不错
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)，没有使用额外的空间
     * <p>
     * <p>
     * 执行结果：通过
     执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     内存消耗：38.6 MB, 在所有 Java 提交中击败了95.75%的用户
     * <p>
     *
     * @return
     */
    public static int[] reversePrint(ListNode head) {
        ListNode curNode = head;
        int length = 0;
        while (curNode != null) {
            length++;
            curNode = curNode.next;
        }
        int[] ints = new int[length];
        curNode = head;
        while (curNode != null) {
            ints[--length] = curNode.val;
            curNode = curNode.next;
        }
        return ints;
    }

    /**
     * 解法2：
     * 思路： 使用栈来实现
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 考虑边界条件：
     * 1、数组为空
     * <p>
     * <p>
     * 执行结果：通过
     * 执行用时：1 ms, 在所有 Java 提交中击败了 83.76% 的用户
     * 内存消耗：46.3 MB, 在所有 Java 提交中击败了 51.08% 的用户
     * <p>
     * <p>
     *
     * @return
     */
    public static int[] reversePrint2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.add(head.val);
            head = head.next;
        }
        int[] ints = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()) {
            ints[i++] = stack.pop();
        }
        return ints;
    }


    /**
     * 解法1：
     * 思路： 循环遍历链表，用容器 ArrayList 装起来,两遍循环
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * <p>
     * 执行结果：通过的用户内存消耗：39.1 MB, 在所有 Java 提交中击败了36.67%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 利用递增的特性，可以使用二分查找法，可以降低时间复杂度至 O(logN)
     *
     * @return
     */
    public static int[] reversePrint1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] ints = new int[list.size()];
        int index = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            ints[index++] = list.get(i);
        }
        return ints;
    }
}
